package com.chapter4.graph.sp;

import java.util.Stack;

/**
 * 
* @ClassName: Topological 
* @Description: 拓扑排序--复习篇 
* @author minjun
* @date 2015年3月14日 下午6:38:00 
*
 */
public class Topological {

	private boolean[] marked;
	
	private Stack<Integer> reversePost;
	
	public Topological(DirectWeightGraph g){
		DirectWeightCycle dwc=new DirectWeightCycle(g);
		if(dwc.hasCycle()){
			throw new RuntimeException("有环，无法进行拓扑排序");
		}
		
		marked=new boolean[g.V()];
		reversePost=new Stack<Integer>();
		for(int i=0;i<g.V();i++){
			if(!marked[i]){
				dfs(g,i);
			}
		}
		
		Stack<Integer> post=new Stack<Integer>();
		while(!reversePost.isEmpty()){
			post.push(reversePost.pop());
		}
		reversePost=post;
	}
	
	private void dfs(DirectWeightGraph g, int v) {
		marked[v]=true;
		for(DirectEdge edge:g.adj(v)){
			int w=edge.to();
			if(!marked[w]){
				dfs(g, w);
			}
		}
		reversePost.push(v);
	}

	public Iterable<Integer> topOrder(){
		return reversePost;
	}
}
